package com.ashin.leetcode;

import org.junit.Test;

/**
 * 寻找中位数
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 算法的时间复杂度应该为 O(log (m+n)) 。
 */
public class L004FindMedianSortedArrays {


    @Test
    public void test() {
        int[] nums1 = {1, 2}, nums2 = {3, 4};
        findMedianSortedArrays(nums1, nums2);
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0 && nums2.length == 0) {
            return 0;
        }
        int[] mergeNums = new int[nums1.length + nums2.length];
        int n1 = 0;
        int n2 = 0;
        for (int i = 0; i < mergeNums.length; i++) {
            if (n1 >= nums1.length) {
                mergeNums[i] = nums2[n2++];
                continue;
            }
            if (n2 >= nums2.length) {
                mergeNums[i] = nums1[n1++];
                continue;
            }

            if (nums1[n1] > nums2[n2]) {
                mergeNums[i] = nums2[n2++];
            } else {
                mergeNums[i] = nums1[n1++];
            }
        }


        return mergeNums.length % 2 == 0 ? (mergeNums[mergeNums.length / 2 - 1] + mergeNums[mergeNums.length / 2]) / 2.0 : mergeNums[mergeNums.length / 2];
    }

}
